package hot;

import java.util.*;


class Node {
     String id;
     double num;

    public Node(String id,double num) {
        this.id = id;
        this.num = num;
    }
}
public class Num399 {
    Map<String,List<Node>> map;
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        map = new HashMap<>();
        for (int i = 0; i < equations.size(); i++) {
            String fat = equations.get(i).get(0);
            String son = equations.get(i).get(1);
            if(!map.containsKey(fat)) {
                map.put(fat,new ArrayList<>());
            }
            if(!map.containsKey(son)) {
                map.put(son,new ArrayList<>());
            }
            map.get(fat).add(new Node(son,values[i]));
            map.get(son).add(new Node(fat,1 / values[i]));
        }
        int cur = 0;
        double[] ans = new double[queries.size()];
        for(List<String> q : queries) {
            ans[cur++] = dfs(q.get(0),q.get(1),1.0,new HashSet<String>());
        }
        return ans;
    }

    private double dfs(String s, String s1, double v, HashSet<String> set) {
        if(!map.containsKey(s) || set.contains(s)) {
            return -1.0;
        }
        if(s.equals(s1)) return v;
        set.add(s);
        for(Node node : map.get(s)) {
            double temp = dfs(node.id,s1,v * node.num,set);
            if(temp != -1.0) return temp;
        }
        return -1.0;
    }
}
